#include <stdlib.h>
#include <string.h>
#include "symtab.h"

// From Donald Knuth's The Art Of Computer Programming Volume 3
static unsigned int hash(char* str, unsigned int len) {
   unsigned int hash = len;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++) {
      hash = ((hash << 5) ^ (hash >> 27)) ^ (*str);
   }
   return (hash & 0x7FFFFFFF);
}

pcg_symtab_t *pcg_symtab_create() {
	int i;
	pcg_symtab_t *st = (pcg_symtab_t *) malloc(sizeof(pcg_symtab_t));
	for (i = 0; i < SYMHASH_SIZE; i++) {
		st->table[i] = NULL;
	}
	
	return st;
}

void pcg_symtab_delete(pcg_symtab_t *st) {
	pcg_sym_t *p, *pn;
	int i;
	
	for (i = 0; i < SYMHASH_SIZE; i++) {
		for (p = st->table[i]; p != NULL; p = pn) {
			pn = p->next;
			free(p);
		}
	}
	
	free(st);
}

void pcg_symtab_insert_symbol(pcg_symtab_t *st, char *name, int arity, void *user_data) {
	pcg_sym_t *symbol, *temp;
	unsigned int bucket;
	
	if (pcg_symtab_lookup(st, name, arity) != NULL) return;
	
	symbol = malloc(sizeof(pcg_sym_t));
	symbol->name = strdup(name);
	symbol->arity = arity;
	symbol->data = user_data;
	symbol->hashv = hash(name, strlen(name));
	bucket = symbol->hashv & SYMHASH_MASK;
	temp = st->table[bucket];
	st->table[bucket] = symbol;
	symbol->next = temp;
	
	st->count++;
}

pcg_sym_t *pcg_symtab_lookup(pcg_symtab_t *st, char *name, int arity) {
	pcg_sym_t *p;
	unsigned int the_hash;
	unsigned int bucket;
	
	the_hash = hash(name, strlen(name));
	bucket = the_hash & SYMHASH_MASK;
	for (p = st->table[bucket]; p != NULL; p = p->next) {
		if (the_hash == p->hashv) {
			if (strcmp(p->name, name) == 0 && arity == p->arity) return p;
		}
	}
	
	return p;
}
